class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }else{
                if(stack.isEmpty()){
                   return false; 
                }
                char ch1 = stack.pop();
                if(!isMatch(ch1,ch)) return false;
            }
        }
        return stack.isEmpty();
    }

    public boolean isMatch(char ch1,char ch2){
        if(ch1 =='(' && ch2 == ')'){
            return true;
        }else if(ch1 =='[' && ch2 == ']'){
            return true;
        }else if(ch1 =='{' && ch2 == '}'){
            return true;
        }
        return false;
    }
}


